package leetcode

import (
	"math"
)

// https://leetcode.com/problems/repeated-dna-sequences/
type Problem string

// findRepeatedDnaSequences brute force.
func findRepeatedDnaSequences(s string) []string {
	res := make([]string, 0)
	exists := make(map[string]int)
	for i := 0; i+10 <= len(s); i++ {
		substr := s[i : i+10]
		exists[substr]++
		if exists[substr] == 2 {
			res = append(res, substr)
		}
	}
	return res
}

// findRepeatedDnaSequences [Rabin–Karp algorithm](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm).
func findRepeatedDnaSequences2(s string) []string {
	res := make([]string, 0)
	exists, nums := make(map[int]int), make([]int, len(s))
	for i := 0; i < len(s); i++ {
		switch s[i : i+1] {
		case "A":
			nums[i] = 0
		case "C":
			nums[i] = 1
		case "G":
			nums[i] = 2
		case "T":
			nums[i] = 3
		}
	}
	strHash := 0
	for left, right := 0, 0; right < len(nums); right++ {
		strHash = strHash*4 + nums[right]
		if right-left+1 == 10 {
			exists[strHash]++
			if exists[strHash] == 2 {
				res = append(res, s[left:right+1])
			}
			strHash = strHash - int(math.Pow(4, 9))*nums[left]
			left++
		}
	}
	return res
}

// func main() {
// 	fmt.Println(findRepeatedDnaSequences("AAAAAAAAAAA"))                      //AAAAAAAAAA
// 	fmt.Println(findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")) //["AAAAACCCCC","CCCCCAAAAA"]
// }
